﻿using DeepEarth.Core;
using System.Collections.Generic;
using System.Linq;
using System;
using System.Windows;
using AnimatingObjectsAlongAPath;
namespace DeepEarth.Toolkit.Geometry
{
    public class Edge
    {
        public Location P1 { get; set; }
        public Location P2 { get; set; }

        public double Vertical
        {
            get
            {
                return P2.Latitude - P1.Latitude;
            }
        }

        public double Horizontal
        {
            get
            {
                return P2.Longitude - P1.Longitude;
            }
        }

        public bool SpansLongitude(double longitude)
        {
            return
                (P1.Longitude > longitude && P2.Longitude < longitude) ||
                (P1.Longitude < longitude && P2.Longitude > longitude);
        }

        public bool SpansEquator()
        {
            return
                (P1.Latitude > 0 && P2.Latitude < 0) ||
                (P1.Latitude < 0 && P2.Latitude > 0);
        }

        public Location IntersectionPoint(double longitude)
        {
            if (!this.SpansLongitude(longitude))
            {
                return null;
            }

            // longitude = P1.Longutude + (u1 * Horizontal)
            // Once I have u1, I can solve for intersection point Lat = P1.Latitude + u1 * Vertical

            double unknown = (longitude - P1.Longitude) / Horizontal;

            double intersectionLat = P1.Latitude + (unknown * Vertical);

            return new Location
            {
                Longitude = longitude,
                Latitude = intersectionLat
            };
        }

        public Location Equatorial()
        {
            if (!this.SpansEquator())
            {
                return null;
            }

            double unknown = (0 - P1.Latitude) / Vertical;
            double intersectionLon = P1.Longitude + (unknown * Horizontal);

            return new Location
            {
                Latitude = 0,
                Longitude = intersectionLon            
            };
        }

        public bool ShareVertex(Edge other)
        {
            return
                other.P1.Equivalent(this.P1) ||
                other.P2.Equivalent(this.P1) ||
                other.P1.Equivalent(this.P2) ||
                other.P2.Equivalent(this.P2);
        }

        // Finds intersection between two edges
        public Location Intersects(Edge other, Func<Location, System.Windows.Point> locationToViewportPoint, Func<Point, Location> viewportPointToLocation)
        {
            Point a = locationToViewportPoint(this.P1);
            Point b = locationToViewportPoint(this.P2);
            Point c = locationToViewportPoint(other.P1);
            Point d = locationToViewportPoint(other.P2);
          
            Line l1 = new Line();
            l1.X1 = a.X;
            l1.Y1 = a.Y;
            l1.X2 = b.X;
            l1.Y2 = b.Y;

            Line l2 = new Line();
            l2.X1 = c.X;
            l2.Y1 = c.Y;
            l2.X2 = d.X;
            l2.Y2 = d.Y;

            System.Windows.Point p = new System.Windows.Point();
            bool intersect = Helpers.DoLinesIntersect(l1, l2, ref p);

            if (intersect)
            {
                return viewportPointToLocation(p);
            }
            else
            {
                return null;
            }

        }
    }

    public class Vector : Edge
    {
        public Location Start
        {
            get { return P1; }
            set { P1 = value; }
        }

        public Location End
        {
            get { return P2; }
            set { P2 = value; }
        }
    }

    public class SimplePolygon
    {
        // Gets a list of ordered locations. If the locations form a self intersecting (or complex) polygon, returns a list of 
        // simple polygons. Assumes the list of locations is closed i.e. first location = last location
        public static List<SimplePolygon> Simplify(List<Location> locations, Func<Location, System.Windows.Point> locationToViewportPoint, Func<Point, Location> viewportPointToLocation)
        {
            List<Vector> vectors = new List<Vector>();
            Location lastLocation = locations[0];

            for (int i = 1; i < locations.Count; i++)
            {
                Vector v = new Vector();
                v.Start = lastLocation;
                v.End = locations[i];
                lastLocation = locations[i];

                if (v.Horizontal != 0 || v.Vertical != 0)
                {
                    vectors.Add(v);
                }
            }

            List<SimplePolygon> simplePolygons = new List<SimplePolygon>();
            List<Vector> potentialSimplePolygon = new List<Vector>();

            // a list of vectors that we know won't be in the current potential polygon and are removed
            // for consideration to avoid errors. Vectors in this list are detected when we find intersections
            List<Vector> excludeList = new List<Vector>();

            while (vectors.Any())
            {
                Vector testVector;

                if (potentialSimplePolygon.Count == 0)
                {
                    testVector = vectors[0];
                }
                else
                {
                    testVector = vectors.Where(v => v.Start == potentialSimplePolygon.Last().End).FirstOrDefault();
                }

                // testVector can be null if there is an internal closed polygon defined. (the minimum number of points needed
                // for this to happen is five.) e.g. draw a pentagram, but now drag one of the points into the main "body" of the pentagram
                // with this kind of shape our simple potentialSimplePolygon generator algorithm can choose between a number of vectors
                // when generating the simple polygon. If it chooses the "wrong" set of vectors, we can leave a set of vectors that cannot
                // be used to define closed polygons. When this happens, we will eventually get a null test vector.
                if (testVector == null)
                {
                    return null;
                }

                vectors.Remove(testVector);

                Vector intersectingVector = null;
                Location intersectionLocation = null;

                foreach (Vector remaining in vectors)
                {
                    if (!testVector.ShareVertex(remaining))
                    {
                        intersectionLocation = testVector.Intersects(remaining, locationToViewportPoint, viewportPointToLocation);

                        if (intersectionLocation != null)
                        {
                            intersectingVector = remaining;
                            break;
                        }
                    }
                }

                if (intersectionLocation == null)
                {
                    potentialSimplePolygon.Add(testVector);

                    // if we have a simple polygon ...
                    if (potentialSimplePolygon.Count > 2 && potentialSimplePolygon[0].Start == potentialSimplePolygon[potentialSimplePolygon.Count - 1].End)
                    {
                        SimplePolygon sp = new SimplePolygon(potentialSimplePolygon);
                        simplePolygons.Add(sp);
                        potentialSimplePolygon.Clear();

                        foreach (Vector e in excludeList)
                        {
                            vectors.Add(e);
                        }

                        excludeList.Clear();
                    }
                }
                else // there was an intersection
                {
                    vectors.Remove(intersectingVector);
                    // Using the intersecting vectors, create 4 new vectors
                    Vector segmentA1, segmentA2, segmentB1, segmentB2;

                    segmentA1 = new Vector
                    {
                        Start = testVector.Start,
                        End = intersectionLocation
                    };

                    segmentA2 = new Vector
                    {
                        Start = intersectionLocation,
                        End = testVector.End
                    };

                    segmentB1 = new Vector
                    {
                        Start = intersectingVector.Start,
                        End = intersectionLocation
                    };

                    segmentB2 = new Vector
                    {
                        Start = intersectionLocation,
                        End = intersectingVector.End
                    };

                    // add vectors to the set of vectors and continue
                    // Although segmentA1 will be the next testVector, we can't just add it to the 
                    // potentialSimplePolygon collection because there may be other intersecting vectors
                    // TODO: Find the flaw in this algorithm requiring these inserts instead of adds.
                    // (Inserts are more efficient anyway, as segmentA1 will be the next testVector but
                    // the algorithm shouldn't require it :O )
                    vectors.Insert(0, segmentA1);
                    //vectors.Add(segmentB1);
                    vectors.Insert(1, segmentB2);

                    // as the testvector is intersected, segment A2 cannot be in the current polygon. Segment A2 and segment b2 will
                    // have the same starting location, we have to remove A2 or else the selection logic for testVector above
                    // can get the wrong vector (we want it to select B2, not A2). We could pull out B1 here as well, but we'll just
                    // do the bare minimum for simplicity.
                    excludeList.Add(segmentA2);
                    excludeList.Add(segmentB1);
                }
            }

            return simplePolygons;
        }

        List<Edge> Edges;

        public SimplePolygon(List<Edge> edges)
        {
            this.Edges = edges;
        }

        public SimplePolygon(List<Vector> vectors)
        {
            this.Edges = vectors.Select(v => v as Edge).ToList();
        }

        public SimplePolygon(List<Location> vertices)
        {
            this.Edges = new List<Edge>();

            int index = 0;

            while (index < vertices.Count - 1)
            {
                Edge e = new Edge
                {
                    P1 = vertices[index],
                    P2 = vertices[index + 1]
                };

                // ignore 0 length edges
                if (e.P1 != e.P2)
                {
                    Edges.Add(e);
                }

                index++;
            }
        }

        public Tuple<List<Edge>, List<Edge>> SpliceAtEquator()
        {
            List<Location> intersectionPoints = new List<Location>();

            List<Edge> processedEdges = new List<Edge>();

            // Split existing edges if they cross the equator
            // otherwise preserve.
            foreach (Edge e in Edges)
            {
                if (e.SpansEquator())
                {
                    Location intersectionPoint = e.Equatorial();
                    intersectionPoints.Add(intersectionPoint);

                    Edge e1 = new Edge
                    {
                        P1 = e.P1,
                        P2 = intersectionPoint
                    };

                    processedEdges.Add(e1);

                    Edge e2 = new Edge
                    {
                        P1 = intersectionPoint,
                        P2 = e.P2
                    };

                    processedEdges.Add(e2);
                }
                else
                {
                    processedEdges.Add(e);
                }
            }

            // As we have spliced the polygon, there will be new edges that run along the equator. Figure out where these will be
            // Need to be careful not to include external edges.
            // this is the list of new Edges that are on the zoneBoundary
            // Note: there are assumptions made about the polygon i.e. no internal intersections i.e. this is a single polygon
            intersectionPoints = intersectionPoints.OrderBy(l => l.Longitude).ToList();

            List<Edge> newBoundaryEdges = new List<Edge>();

            int index = 0;
            while (index < intersectionPoints.Count - 1)
            {
                Edge border = new Edge
                {
                    P1 = intersectionPoints[index],
                    P2 = intersectionPoints[index + 1]
                };

                newBoundaryEdges.Add(border);

                // jump by two - the number of intersections should aways be even, pairs of points make up a new zone boundary.
                // Need to create edges using the correct points. Basically P1 is even index, P2 is odd index (0 is even for this purpose)
                index += 2;
            }

            // Partition the edges using the zone boundary
            List<Edge> north = new List<Edge>();
            List<Edge> south = new List<Edge>();

            foreach (Edge e in processedEdges)
            {
                // can't use >= test because some edges will terminate on the boundary and we need to figure out
                // which side it really belongs
                if (e.P1.Latitude > 0 || e.P2.Latitude > 0)
                {
                    north.Add(e);
                }
                else
                {
                    south.Add(e);
                }
            }

            foreach (Edge e in newBoundaryEdges)
            {
                north.Add(e);
                south.Add(e);
            }

            return new Tuple<List<Edge>, List<Edge>>(north, south);
        }

        public Tuple<List<Edge>, List<Edge>> Splice(double zoneBoundary)
        {
            List<Location> intersectionPoints = new List<Location>();

            List<Edge> processedEdges = new List<Edge>();

            bool edgeAdded = false;
            // Split existing edges if they cross the zone boundary
            // otherwise preserve.
            foreach (Edge e in Edges)
            {
                if (e.SpansLongitude(zoneBoundary))
                {
                    Location intersectionPoint = e.IntersectionPoint(zoneBoundary);
                    intersectionPoints.Add(intersectionPoint);

                    Edge e1 = new Edge
                    {
                        P1 = e.P1,
                        P2 = intersectionPoint
                    };

                    processedEdges.Add(e1);

                    Edge e2 = new Edge
                    {
                        P1 = intersectionPoint,
                        P2 = e.P2
                    };

                    processedEdges.Add(e2);

                    edgeAdded = true;
                }
                else
                {
                    processedEdges.Add(e);
                }
            }

            if (!edgeAdded)
            {
                // no splicing occurred
                // return early here so we don't have to figure out whether an edge that corresponds
                // to a boundary was inserted by us, or whether it is part of the original polygon.
                return new Tuple<List<Edge>, List<Edge>>(processedEdges, new List<Edge>());
            }

            // As we have spliced the polygon, there will be new edges that run along the zone boundary. Figure out where these will be
            // Need to be careful not to include external edges.
            // this is the list of new Edges that are on the zoneBoundary
            intersectionPoints = intersectionPoints.OrderBy(l => l.Latitude).ToList();

            List<Edge> newBoundaryEdges = new List<Edge>();

            int index = 0;
            while (index < intersectionPoints.Count - 1)
            {
                Edge border = new Edge
                {
                    P1 = intersectionPoints[index],
                    P2 = intersectionPoints[index + 1]
                };

                newBoundaryEdges.Add(border);

                // jump by two - the number of intersections should aways be even, pairs of points make up a new zone boundary.
                // Need to create edges using the correct points. Basically P1 is even index, P2 is odd index (0 is even for this purpose)
                index += 2;
            }

            // Partition the edges using the zone boundary
            List<Edge> left = new List<Edge>();
            List<Edge> right = new List<Edge>();

            foreach (Edge e in processedEdges)
            {
                if (e.P1.Longitude < zoneBoundary || e.P2.Longitude < zoneBoundary)
                {
                    left.Add(e);
                }
                else
                {
                    right.Add(e);
                }
            }

            foreach (Edge e in newBoundaryEdges)
            {
                left.Add(e);
                right.Add(e);
            }

            return new Tuple<List<Edge>, List<Edge>>(left, right);
        }

        public static List<SimplePolygon> FindCircuits(List<Edge> edges)
        {
            if (edges == null || edges.Count == 0)
            {
                return null;
            }

            List<SimplePolygon> completePolygons = new List<SimplePolygon>();

            Edge firstEdge = edges[0];
            edges.Remove(firstEdge);

            List<Edge> potentialCircuit = new List<Edge>();
            potentialCircuit.Add(firstEdge);

            Edge lastEdge = firstEdge;

            while (edges.Any())
            {
                Edge connector = edges.Where(e => lastEdge.ShareVertex(e)).FirstOrDefault();

                potentialCircuit.Add(connector);
                edges.Remove(connector);

                lastEdge = connector;

                // test for a complete circuit
                if (potentialCircuit.Count > 2 && firstEdge.ShareVertex(connector))
                {
                    completePolygons.Add(new SimplePolygon(potentialCircuit));

                    var others = FindCircuits(edges);

                    if (others != null)
                    {
                        completePolygons = completePolygons.Concat(others).ToList();
                    } 
                }
            }
            return completePolygons;
        }

        public List<Location> GetVertices()
        {
            List<Location> vertices = new List<Location>();

            List<Edge> clonedEdges = new List<Edge>();
            foreach (var edge in Edges)
            {
                clonedEdges.Add(edge);
            }

            if (clonedEdges.Any())
            {
                Edge currentEdge = clonedEdges[0];
                clonedEdges.Remove(currentEdge);

                vertices.Add(currentEdge.P1);
                vertices.Add(currentEdge.P2);

                Location firstVertex = currentEdge.P1;
                Location currentVertex = currentEdge.P2;

                while (true)
                {
                    Edge nextEdge = clonedEdges.Where(e => e.P1 == currentVertex || e.P2 == currentVertex).FirstOrDefault();

                    if (nextEdge.P1 == currentVertex)
                    {
                        vertices.Add(nextEdge.P2);
                        currentVertex = nextEdge.P2;
                    }
                    else
                    {
                        vertices.Add(nextEdge.P1);
                        currentVertex = nextEdge.P1;
                    }

                    currentEdge = nextEdge;
                    clonedEdges.Remove(currentEdge);

                    if (currentVertex == firstVertex)
                    {
                        break;
                    }
                }
            }

            return vertices;

        }
    }
}
